package com.harvey.study.data.structure.datastructure.queue;

/**
 * 
 * date: 2021-04-27
 * desc: 队列 通过数据的方式实现，
 * 并通过指针循环指向的方式解决空间浪费问题
 * 
 * 下面实现方式是在循环队列中少用一个元素的存储空间，
 * 约定以对尾指针加1等于队头指针表示队列已满
 */
public class LoopQueue<T> {
    private final static int defaultSize = 5;//默认初始化栈表长度
    private int front;
    private int rear;
    private T[] queueArray;

    public LoopQueue() {
        this.queueArray = (T[]) new Object[defaultSize];
    }

    public void enQueue(T data){
        if((rear+1)%queueArray.length == front){ 
            //表示队列满了，先扩容
            expansion();
        }
        rear = (rear+1)%queueArray.length;
        queueArray[rear] = data;

    }

    public T deQueue(){
        if(isEmpty()){
            return null;
        }
        front = (front+1)%queueArray.length;
        return queueArray[front];
    }

    public int size(){
        return (rear-front+queueArray.length)%queueArray.length;
    }

    public boolean isEmpty(){
        return front == rear;
    }


    /**
     * 扩容
     */
    public void expansion(){
        T[] newArray = (T[]) new Object[queueArray.length*2];
        for(int i=0;i<queueArray.length;i++){
            T p = deQueue();
            if(p == null){
                break;
            }
            newArray[i+1] = p;
            System.out.println("for:"+p);
        }
        front = 0;
        queueArray = newArray;
    }

    public static void main(String[] args) {
        LoopQueue<String> singleQueue = new LoopQueue<String>();

        singleQueue.enQueue("A");
        singleQueue.enQueue("B");
        singleQueue.enQueue("C");
        singleQueue.enQueue("D");
        singleQueue.enQueue("E");

        singleQueue.enQueue("A");
        singleQueue.enQueue("B");
        singleQueue.enQueue("C");
        singleQueue.enQueue("D");
        singleQueue.enQueue("E");


        singleQueue.enQueue("A");
        singleQueue.enQueue("B");
        singleQueue.enQueue("C");
        singleQueue.enQueue("D");
        singleQueue.enQueue("E");

        singleQueue.enQueue("A");
        singleQueue.enQueue("B");
        singleQueue.enQueue("C");
        singleQueue.enQueue("D");
        singleQueue.enQueue("E");

        singleQueue.enQueue("A");
        singleQueue.enQueue("B");
        singleQueue.enQueue("C");
        singleQueue.enQueue("D");
        singleQueue.enQueue("E");


        singleQueue.enQueue("A");
        singleQueue.enQueue("B");
        singleQueue.enQueue("C");
        singleQueue.enQueue("D");
        singleQueue.enQueue("E");


        System.out.println(singleQueue.size());

        int size = singleQueue.size();
        for(int i=0;i<size;i++){
            String p = singleQueue.deQueue();
            System.out.println(p);
        }

        System.out.println(singleQueue.size());


    }
    
}
